#include <vector>
#include <iostream>
#include <string>
using namespace std;

struct TreeNode
{
    TreeNode* left;
    TreeNode* right;
    int val;
    TreeNode(int pval) :left(nullptr), right(nullptr), val(pval)
    {}
};
//
//struct ListNode {
//    int val;
//    struct ListNode* next;
//    ListNode(int x) : val(x), next(nullptr) {}
//};
//
//class Solution {
//public:
//    void front(TreeNode* root, vector<int>& ret)
//    {
//        if (root == nullptr)
//        {
//            return;
//        }
//        ret.push_back(root->val);
//        front(root->left, ret);
//        front(root->right, ret);
//    }
//
//    vector<int> preorderTraversal(TreeNode* root) {
//        // write code here
//        vector<int> ret;
//        front(root, ret);
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    void front(TreeNode* root, vector<int>& ret)
//    {
//        if (root == nullptr)
//        {
//            return;
//        }
//        front(root->left, ret);
//        ret.push_back(root->val);
//        front(root->right, ret);
//    }
//
//    vector<int> inorderTraversal(TreeNode* root) {
//        // write code here
//        vector<int> ret;
//        front(root, ret);
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    int Size(ListNode*& head)
//    {
//        ListNode* cur = head;
//        int i = 0;
//        while (cur)
//        {
//            i++;
//            cur = cur->next;
//        }
//        return i;
//    }
//    ListNode* rotateLinkedList(ListNode* head, int k) {
//        // write code here
//        int n = Size(head);
//        k = k % n;
//        if (k == 0 || head == nullptr)
//        {
//            return head;
//        }
//        ListNode* prev = nullptr;
//        ListNode* cur = head;
//        ListNode* phead = nullptr;
//        int i = n - k;
//        while (cur)
//        {
//            i--;
//            prev = cur;
//            cur = cur->next;
//            if (i == 0)
//            {
//                prev->next = nullptr;
//                phead = cur;
//            }
//        }
//        prev->next = head;
//        return phead;
//    }
//};
//
//class Solution {
//public:
//    void front(TreeNode* root, vector<int>& ret)
//    {
//        if (root == nullptr)
//        {
//            return;
//        }
//        front(root->left, ret);
//        front(root->right, ret);
//        ret.push_back(root->val);
//    }
//    vector<int> postorderTraversal(TreeNode* root) {
//        // write code here
//        vector<int> ret;
//        front(root, ret);
//        return ret;
//    }
//};
//
//class Solution {
//public:
//    void curing(TreeNode* root, TreeNode*& phead, TreeNode*& prev)
//    {
//        if (root == nullptr)
//        {
//            return;
//        }
//        curing(root->left, phead, prev);
//        TreeNode* cur = root->right;
//        if (phead == nullptr)
//        {
//            phead = root;
//        }
//        root->left = prev;
//        if (prev)
//        {
//            prev->right = root;
//        }
//        prev = root;
//        curing(cur, phead, prev);
//    }
//
//    TreeNode* Convert(TreeNode* pRootOfTree) {
//        TreeNode* phead = nullptr;
//        TreeNode* prev = nullptr;
//        curing(pRootOfTree, phead, prev);
//        return phead;
//    }
//};
//
//class Solution {
//public:
//    TreeNode* MakeNode(TreeNode* t1, TreeNode* t2)
//    {
//        if (t1 == nullptr && t2 == nullptr)
//        {
//            return nullptr;
//        }
//        if (t1 == nullptr)
//        {
//            return t2;
//        }
//        if (t2 == nullptr)
//        {
//            return t1;
//        }
//        TreeNode* cur = new TreeNode(t1->val + t2->val);
//        cur->left = MakeNode(t1->left, t2->left);
//        cur->right = MakeNode(t1->right, t2->right);
//        delete t1, t2;
//        return cur;
//    }
//
//    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
//        // write code here
//        return MakeNode(t1, t2);
//    }
//};

class Solution {
public:
    void _Serialize(TreeNode* root, vector<char> ret)
    {
        if (root == nullptr)
        {
            ret.push_back('#');
            return;
        }
        ret.push_back(root->val + '0');
        _Serialize(root->left, ret);
        _Serialize(root->right, ret);
    }
    char* Serialize(TreeNode* root)
    {
        vector<char> ret;
        _Serialize(root, ret);
        int n = ret.size();
        char* tree = new char[n];
        for (int i = 0; i < n; i++)
        {
            tree[i] = ret[i];
        }
        return tree;
    }
    TreeNode* _Deserialize(char* str, int& i, int n)
    {
        if (str[i] == '#' || i >= n)
        {
            return nullptr;
        }
        TreeNode* root = new TreeNode(str[i] - '0');
        root->left = _Deserialize(str, ++i, n);
        root->right = _Deserialize(str, ++i, n);
        return root;
    }
    TreeNode* Deserialize(char* str) {
        int i = 0;
        int n = strlen(str);
        cout << n;
        return _Deserialize(str, i, n);
    }
};

int main()
{
    char arr[] = { "123##67"};
    Solution s;
    s.Deserialize(arr);
    return 0;
}